As is known in the art, deliberative decision-making often relies on a plan: a sequence of parameterized actions that lead from an initial state to a desired goal state. The plan breaks high-level goals into smaller goals that are more easily attained, and that together achieve the overall goal. Planning is a search in a state space that is exponential in the number of features, which is intractable in general; thus, it is critically important for scalability to be able to focus the search intelligently.
Various planner systems are known in the art. For example, the Graphplan planning graph heuristic improved the efficiency of planning in propositional state spaces by ignoring the delete effects of each so-called STRIPS-style action. This relaxation is solved efficiently and provides a good lower bound for the solution to the harder unrelaxed problem. When time and numeric resources were added to the third International Planning Competition (IPC-3) in 2002, it was natural to figure out ways to make a similar relaxation in the metric domain. The techniques used by planners such as Metric-FF, Sapa, and LPG were successful in IPC-3. But when they converted the relaxed plan computation (which is based on earliest time) into a computation for a bound on the metric (lowest cost) there was an opportunity to tighten the bounds, meaning that in theory more searching was being done than was needed.
It is believed that current approaches to plan graph construction for metric optimization domains are specifically tied to the concurrent properties of time. An action A is applied when its preconditions are true, and a calculation is made to update the earliest time any fact in action A's effects can be achieved. This is the maximum time over each of the preconditions plus the duration d of the action, or, t=max∀pεpre(A) (time(p))+d. The time of each fact in action A's add effects is then updated if t improves on the earliest time of the fact.
While this may work for minimizing time, it breaks down when applied to fluents that describe quantities of physical substances or even intangibles like energy use. For example, if one were trying to minimize energy use instead of time, taking the maximum over the energy used to establish each fact in A's preconditions is still a safe, admissible bound, but a tighter bound would be a sum of the energy use of the preconditions, not a maximum. This is because most numeric variables track consumable resources whose use is unaffected by concurrency. But in general, sum-propagation is inadmissible because it overcounts the contribution of any action that contributes to the establishment of two or more preconditions of a future action.
The Metric-FF planner provided the argument that the propositional technique of “ignoring delete lists” could be extended to numeric fluents by representing fluents as a range of real values that can only be expanded (and not shrunk) by the application of actions. But a method for applying this has been elusive. This interpretation is analogous to the propositional relaxed plan.